Nửa nhóm là gì? Các bài báo nghiên cứu khoa học liên quan

Định nghĩa nửa nhóm

Nửa nhóm (submonoid) là tập con N của một monoid M sao cho N đóng kín dưới phép nhân và chứa đơn vị của M. Cụ thể, nếu (M, ·, e) là một monoid, thì N ⊆ M là nửa nhóm khi thỏa mãn hai điều kiện:

• Đơn vị e của M thuộc N;
• Với mọi a, b ∈ N, tích a·b cũng thuộc N.

Do phép nhân trong M đã có tính kết hợp, N kế thừa tính kết hợp này. Khái niệm nửa nhóm rất quan trọng trong đại số cấu trúc vì cho phép nghiên cứu các tập con có cấu trúc đóng, tương tự như nhóm con nhưng không yêu cầu tồn tại phần tử nghịch đảo.

Ví dụ điển hình

Trong monoid (ℕ₀, +, 0) của các số tự nhiên với phép cộng, mỗi tập kℕ₀ = {0, k, 2k, 3k, …} với k ∈ ℕ₊ là một nửa nhóm con điển hình. Tập này chứa 0 và đóng dưới phép cộng, vì tổ hợp hai bội của k vẫn là bội của k.

Với monoid (ℕ, ·, 1) của các số tự nhiên với phép nhân, tập {1, p, p², p³, …} với p nguyên tố là nửa nhóm sinh bởi p. Mọi phần tử trong tập này đều có dạng p^n và tích của hai phần tử p^m·p^n = p^(m+n) vẫn nằm trong tập.

Ví dụ khác: trong tập các ma trận vuông 2×2 khả nghịch GL₂(ℝ), tập con các ma trận có xác định thức dương tạo nên một nửa nhóm, vì tích của hai ma trận có định thức dương vẫn có định thức dương và chứa ma trận đơn vị I₂.

Tính chất đại số

Nửa nhóm kế thừa hầu hết tính chất của monoid gốc, trừ tính nghịch đảo. Cụ thể:

• Đóng: ∀a, b ∈ N, a·b ∈ N.
• Kết hợp: a·(b·c) = (a·b)·c cho mọi a, b, c ∈ N.
• Chứa đơn vị: e ∈ N.

Không bắt buộc mỗi phần tử trong N phải có phần tử nghịch đảo. Vì vậy, nửa nhóm không yêu cầu ∀a ∈ N tồn tại a⁻¹ ∈ N sao cho a·a⁻¹ = e. Điều này phân biệt nửa nhóm với nhóm con, mở rộng khả năng áp dụng cho các tập chỉ yêu cầu đóng dưới một phép toán đơn giản.

Tính chất đóng và kết hợp cho phép xây dựng các cấu trúc phức tạp hơn như nửa vành (semiring), khi kết hợp một nửa nhóm với phép cộng, hoặc nghiên cứu các ideals trong đại số trừu tượng.

Nửa nhóm sinh ra và hệ sinh

Cho M là monoid và S ⊆ M một tập con, nửa nhóm sinh ra bởi S, ký hiệu ⟨S⟩, là giao của tất cả các nửa nhóm chứa S. Cũng có thể mô tả bằng tập tất cả các tích hữu hạn gồm các phần tử của S kèm thêm đơn vị e:

$\langle S\rangle \;=\;\bigcap_{\substack{N\le M\\S\subseteq N}} N \;=\;\{\,e,\,s_1\cdot s_2\cdots s_k \mid s_i\in S,\;k\ge1\}.$

Hệ sinh S xác định cách tạo mọi phần tử trong ⟨S⟩ qua phép nhân lặp. Trong thực hành, danh sách các phần tử sinh được có thể biểu diễn bằng cây phân tích cú pháp (parse tree) hoặc đồ thị Cayley nếu M là monoid tự do.

Nửa nhóm sinh ra là công cụ cơ bản để xác định nửa nhóm tối thiểu chứa S, tương tự như khái niệm generated submonoid trong lý thuyết nhóm. Trong lý thuyết ngôn ngữ hình thức, nửa nhóm sinh bởi tập các ký tự X chính là X*, tập hợp mọi xâu hữu hạn trên X.

Đồng hình và ảnh ngược

Giả sử φ: M → M′ là một đồng hình monoid giữa hai monoid (M, ·, e) và (M′, ⋆, e′). Khi đó, ảnh của một nửa nhóm N ≤ M dưới φ là φ(N) = {φ(n) | n ∈ N}, và φ(N) ≤ M′ vì:

• φ(e) = e′ ∈ φ(N);
• với bất kỳ a′, b′ ∈ φ(N), tồn tại a, b ∈ N sao cho φ(a) = a′, φ(b) = b′, do đó a′ ⋆ b′ = φ(a) ⋆ φ(b) = φ(a·b) ∈ φ(N).

Ngược lại, cho N′ ≤ M′, ảnh ngược φ⁻¹(N′) = {m ∈ M | φ(m) ∈ N′} là một nửa nhóm con của M, vì:

• e ∈ φ⁻¹(N′) do φ(e) = e′ ∈ N′;
• với a, b ∈ φ⁻¹(N′), φ(a·b) = φ(a) ⋆ φ(b) ∈ N′ nên a·b ∈ φ⁻¹(N′).

Đồng hình và ảnh ngược cho phép xây dựng các công cụ đại số để so sánh cấu trúc nửa nhóm giữa các monoid khác nhau, cũng như phân tích tính chất bảo toàn (preservation) của các tính chất nửa nhóm qua các ánh xạ.

Nửa nhóm tự do

Nửa nhóm tự do trên tập X ký hiệu X* là monoid của tất cả các xâu hữu hạn (có độ dài ≥ 0) trên X với phép nối chuỗi (concatenation) và đơn vị là xâu rỗng ε. X* thỏa mãn tính chất phổ quát (universal property): với mọi ánh xạ φ: X → M (vào một monoid M bất kỳ), tồn tại duy nhất một đồng hình monoid φ̄: X* → M sao cho φ̄(x) = φ(x) với mọi x ∈ X.

Cấu trúc của X* rất dễ hình dung qua cây Cayley: mỗi đỉnh là một xâu, mỗi cung nối xâu s với s·x (x ∈ X). Độ dài xâu tương ứng với khoảng cách từ gốc ε.

• Đơn vị: ε.
• Phép nhân: nối chuỗi, bất kỳ a, b ∈ X*, a·b ∈ X*.
• Nếu X = {a, b}, X* = {ε, a, b, aa, ab, ba, bb, …}.

Nửa nhóm tự do là nền tảng cho ngôn ngữ hình thức, tự động hữu hạn và lý thuyết văn phạm, cho phép mô tả ngôn ngữ và quy tắc sinh xâu.

Vấn đề xác định thành viên

Cho monoid M và tập sinh S ⊆ M, bài toán quyết định xem một phần tử m ∈ M có thuộc nửa nhóm ⟨S⟩ hay không có thể khác nhau về độ phức tạp tùy vào cấu trúc M:

• Trong monoid tự do X*, quyết định m ∈ ⟨S⟩ tương đương bài toán ghép xâu: liệu xâu m có biểu diễn được dưới dạng tích các xâu trong S hay không, có thuật toán quy hoạch động O(|m|·|S|·L) với L là độ dài tối đa của xâu sinh.
• Trong monoid tổng quát (ví dụ monoid ma trận khả nghịch), vấn đề này là NP-đủ hoặc thậm chí undecidable nếu M có cấu trúc phức tạp như monoid tự do hai chiều.

Để khảo sát hiệu quả, có thể xây dựng đồ thị trạng thái hoặc automaton sao chép phép sản sinh, sau đó tìm đường đi từ e đến m. Tuy nhiên, độ lớn của đồ thị thường khai triển lũy thừa, gây tốn bộ nhớ và thời gian.

Ứng dụng

• Lý thuyết ngôn ngữ hình thức: X* và các nửa nhóm sinh (submonoid) giúp mô hình hóa ngôn ngữ chính quy, ngữ pháp phi ngữ cảnh, và tự động hữu hạn.
• Mật mã học: nửa nhóm của các thao tác mã hóa, giải mã an toàn sử dụng trong thiết kế giao thức và chứng minh bảo mật.
• Tối ưu hóa quy trình sản xuất: mô hình trạng thái máy (state machine) với nửa nhóm các phép biến đổi, giúp phân tích khả năng đạt trạng thái mục tiêu.
• Khoa học máy tính: nghiên cứu mô hình tính toán (thí dụ λ-calculus), nơi nửa nhóm biểu diễn các phép biến đổi biểu thức.

Qua các lĩnh vực, nửa nhóm cho phép trừu tượng hóa quy tắc kết hợp tác động, giúp phân tích tính đóng gói, tính phân phối và tìm kiếm các đoạn lặp lại (loops) trong hệ thống.

Hướng nghiên cứu tương lai

Mở rộng khái niệm nửa nhóm cho các cấu trúc đa đại lượng (polyadic monoids) và monoid với đa phép toán, nhằm nghiên cứu tính đóng và cấu trúc sinh trong bối cảnh đại số bậc cao. Nghiên cứu ứng dụng vào lý thuyết category giúp kết nối nửa nhóm với khái niệm đối tượng và các chuẩn tắc (monoidal categories).

Phát triển thuật toán xác định thành viên hiệu quả cho monoid phức tạp trong hệ phân tán (distributed systems), tận dụng kỹ thuật đồng thuận và bản đồ trạng thái phân tán (distributed hash table) để theo dõi phần tử sinh.

• Phương pháp học máy (machine learning) đánh giá cấu trúc nửa nhóm dựa trên mẫu dữ liệu, hỗ trợ dự đoán khả năng sinh m mà không cần duyệt toàn bộ không gian trạng thái.
• Ứng dụng trong mã hóa lượng tử (quantum cryptography), nghiên cứu nửa nhóm các phép toán unitary trong không gian Hilbert, mở đường cho giao thức bảo mật mới.

Sự giao thoa giữa đại số trừu tượng, khoa học máy tính và công nghệ mới tạo ra tiềm năng phát triển lý thuyết nửa nhóm và ứng dụng trong đời sống và khoa học tự nhiên.